{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 26.4 Push-relabel algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 26.4-1\n",
    "\n",
    "> Prove that, after the procedure INITIALIZE-PREFLOW$(G, S)$ terminates, we have $s.e \\le -|f^*|$, where $f^*$ is a maximum flow for $G$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 26.4-2\n",
    "\n",
    "> Show how to implement the generic push-relabel algorithm using $O(V)$ time per relabel operation, $O(1)$ time per push, and $O(1)$ time to select an applicable operation, for a total time of $O(V^2E)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 26.4-3\n",
    "\n",
    "> Prove that the generic push-relabel algorithm spends a total of only $O(VE)$ time in performing all the $O(V^2)$ relabel operations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 26.4-4\n",
    "\n",
    "> Suppose that we have found a maximum flow in a flow network $G = (V, E)$ using a push-relabel algorithm. Give a fast algorithm to find a minimum cut in $G$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 26.4-5\n",
    "\n",
    "> Give an efficient push-relabel algorithm to find a maximum matching in a bipartite graph. Analyze your algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 26.4-6\n",
    "\n",
    "> Suppose that all edge capacities in a flow network $G = (V, E)$ are in the set $\\{ 1, 2, \\dots, k \\}$. Analyze the running time of the generic push-relabel algorithm in terms of $|V|$, $|E|$, and $k$. (Hint: How many times can each edge support a nonsaturating push before it becomes saturated?)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 26.4-7\n",
    "\n",
    "> Show that we could change line 6 of INITIALIZE-PREFLOW to \n",
    "> \n",
    "> `6  s.h = |G.V| - 2` \n",
    "> \n",
    "> without affecting the correctness or asymptotic performance of the generic pushrelabel algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 26.4-8\n",
    "\n",
    "> Let $\\delta_f(u, v)$ be the distance (number of edges) from $u$ to $v$ in the residual network $G_f$. Show that the GENERIC-PUSH-RELABEL procedure maintains the properties that $u.h < |V|$ implies $u.h \\le \\delta_f(u, t)$ and that $u.h \\ge |V|$ implies $u.h - |V| \\le \\delta_f(u, s)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 26.4-9 $\\star$\n",
    "\n",
    "> As in the previous exercise, let $\\delta_f(u, v)$ be the distance from $u$ to $v$ in the residual network $G_f$. Show how to modify the generic push-relabel algorithm to maintain the property that $u.h < |V|$ implies $u.h = \\delta_f(u, t)$ and that $u.h \\ge |V|$ implies $u.h - |V| = \\delta_f(u, s)$. The total time that your implementation dedicates to maintaining this property should be $O(VE)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 26.4-10\n",
    "\n",
    "> Show that the number of nonsaturating pushes executed by the GENERIC-PUSH-RELABEL procedure on a flow network $G = (V, E)$ is at most $4|V|^2|E|$ for $|V| \\ge 4$."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
